class Solution {
public:
    bool isValid(string s) 
    {
        stack<char> st;
        map<char,char> countMap;
        countMap['['] = ']';
        countMap['{'] = '}';
        countMap['('] = ')';

        for(auto &e : s)
        {
            if(countMap.count(e))//左括号入栈
            {
                st.push(e);
            }
            else//有括号匹配
            {

                if(st.empty())
                    return false;
                char topVal = st.top();
                st.pop();
                if(countMap[topVal] != e)
                    return false; 
            }
        }
        return st.empty();
    }
};
/*
// Definition for a Node.
class Node {
public:
    int val;
    Node* next;
    Node* random;
    
    Node(int _val) {
        val = _val;
        next = NULL;
        random = NULL;
    }
};
*/

class Solution {
public:
    Node* copyRandomList(Node* head) 
    {
        map<Node*,Node*> nodeCopyMap;
        Node* copyHead = nullptr;
        Node* copyTail = nullptr;    

        //拷贝链表
        Node* cur = head;
        while(cur)
        {
            Node* copyNode = new Node(cur->val);
            if(copyHead == nullptr)
            {
                copyHead = copyTail = copyNode;
            }
            else
            {
                copyTail->next = copyNode;
                copyTail = copyTail->next;
            }
            nodeCopyMap[cur] = copyNode;
            cur = cur->next;
        }

        //处理random
        cur = head;
        copyTail = copyHead;
        while(cur)
        {
            if(cur->random == nullptr)
            {
                copyTail->random = nullptr;
            }
            else
            {
                copyTail->random = nodeCopyMap[cur->random];
            }
            cur = cur->next;
            copyTail = copyTail->next;
        }
        return copyHead;
    }
};

class Solution {
public:
    vector<int> intersection(vector<int>& nums1, vector<int>& nums2)
    {
        set<int> s1,s2;
        vector<int> res;
        for(auto &e: nums1)
        {
            s1.insert(e);
        }
        for(auto &e: nums2)
        {
            s2.insert(e);
        }
        auto it1 = s1.begin();
        auto it2 = s2.begin();

        while(it1 != s1.end() && it2 != s2.end())
        {
            if(*it1 < *it2)
                it1++;
            else if(*it1 > *it2)
                it2++;
            else
            {
                res.push_back(*it2);
                ++it1;
                ++it2;
            }
        }
        return res;
    }   
};
class Solution {
public:
    int subarraySum(vector<int>& nums, int k) 
    {
        unordered_map<int,int> hash;
        hash[0] = 1;
        int sum = 0,ret = 0;

        for(auto e : nums)
        {
            sum+=e;//统计当前位置前缀和
            if(hash.count(sum - k))
                ret += hash[sum-k];//统计个数
 
            hash[sum]++;
        }
        return ret;
    }
};

class Solution {
public:
    int subarraysDivByK(vector<int>& nums, int k) 
    {
        unordered_map<int,int> hash;
        hash[0] = 1;
        int sum = 0, ret = 0;
        for(auto e : nums)
        {
            sum+=e;
            int r =( sum % k + k ) % k;//修正后余数
            if(hash.count(r))
                ret += hash[r];
            hash[r]++;
        }
        return ret;
    }
};
